import java.util.*;
 // 力扣433. 最小基因变化
class Solution {
    /**
     * 计算从起始基因到目标基因所需的最小突变次数
     * 每次突变只能改变一个字符，且突变结果必须在基因库中存在
     *
     * @param startGene 起始基因字符串
     * @param endGene 目标基因字符串
     * @param bank 基因库，存储所有允许的基因字符串
     * @return 最小突变次数，若无法达到目标则返回-1
     */
    public int minMutation(String startGene, String endGene, String[] bank) {
        // 将基因库转换为HashSet，提高查询效率
        Set<String> bankSet = new HashSet<>(Arrays.asList(bank));

        // 如果目标基因不在基因库中，直接返回-1（无法达成）
        if (!bankSet.contains(endGene)) {
            return -1;
        }

        // 用于BFS的队列，存储当前需要处理的基因
        Queue<String> queue = new LinkedList<>();
        // 用于记录已访问过的基因，避免重复处理
        Set<String> visited = new HashSet<>();

        // 初始化队列，将起始基因加入并标记为已访问
        queue.offer(startGene);
        visited.add(startGene);

        // 记录突变步数
        int steps = 0;

        // BFS循环，直到队列为空（所有可能路径都已探索）
        while (!queue.isEmpty()) {
            // 当前层的基因数量
            int size = queue.size();

            // 处理当前层的所有基因
            for (int i = 0; i < size; i++) {
                // 取出队列中的第一个基因
                String currentGene = queue.poll();

                // 如果当前基因就是目标基因，返回当前步数
                if (currentGene.equals(endGene)) {
                    return steps;
                }

                // 尝试对当前基因的每个位置进行突变
                for (int j = 0; j < currentGene.length(); j++) {
                    // 可能的基因字符：A、C、G、T
                    for (char c : new char[] {'A', 'C', 'G', 'T'}) {
                        // 跳过与当前字符相同的突变（无意义的突变）
                        if (c != currentGene.charAt(j)) {
                            // 生成新的基因：替换第j个字符为c
                            String newGene = currentGene.substring(0, j) + c + currentGene.substring(j + 1);

                            // 若新基因在基因库中且未被访问过，则加入队列并标记为已访问
                            if (bankSet.contains(newGene) && !visited.contains(newGene)) {
                                visited.add(newGene);
                                queue.offer(newGene);
                            }
                        }
                    }
                }
            }

            // 完成当前层的处理后，步数加1
            steps++;
        }

        // 若队列空了仍未找到目标基因，返回-1
        return -1;
    }
}



// 力扣127. 单词接龙
class Solution1 {
    /**
     * 计算从 beginWord 到 endWord 的最短转换序列长度
     * 转换规则：每次只能改变一个字母，转换得到的单词必须在 wordList 中
     *
     * @param beginWord 起始单词
     * @param endWord 目标单词
     * @param wordList 可用单词列表
     * @return 最短转换序列的长度，若无法转换则返回0
     */
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        // 将单词列表转换为HashSet，提高查询效率（O(1)时间复杂度）
        Set<String> wordSet = new HashSet<>(wordList);

        // 如果目标单词不在单词列表中，直接返回0（无法完成转换）
        if (!wordSet.contains(endWord)) {
            return 0;
        }

        // BFS队列：存储当前需要处理的单词
        Queue<String> queue = new LinkedList<>();
        // 已访问集合：记录已处理过的单词，避免重复处理和循环路径
        Set<String> visited = new HashSet<>();

        // 初始化队列，将起始单词加入并标记为已访问
        queue.offer(beginWord);
        visited.add(beginWord);

        // 记录转换步数（初始为1，因为包含起始单词本身）
        int steps = 1;

        // BFS主循环：直到队列为空（所有可能路径都已探索）
        while (!queue.isEmpty()) {
            // 当前层的单词数量（用于分层处理）
            int size = queue.size();

            // 处理当前层的所有单词
            for (int i = 0; i < size; i++) {
                // 取出队列中的第一个单词
                String currentWord = queue.poll();

                // 如果当前单词就是目标单词，返回当前步数
                if (currentWord.equals(endWord)) {
                    return steps;
                }

                // 尝试改变当前单词的每个字符位置
                for (int j = 0; j < currentWord.length(); j++) {
                    // 尝试从 'a' 到 'z' 的所有可能字符
                    for (char c = 'a'; c <= 'z'; c++) {
                        // 跳过与当前字符相同的替换（无意义的转换）
                        if (c != currentWord.charAt(j)) {
                            // 生成新单词：替换第j个字符为c
                            String newWord = currentWord.substring(0, j) + c + currentWord.substring(j + 1);

                            // 若新单词在单词列表中且未被访问过，则加入队列并标记为已访问
                            if (wordSet.contains(newWord) && !visited.contains(newWord)) {
                                visited.add(newWord);
                                queue.offer(newWord);
                            }
                        }
                    }
                }
            }

            // 完成当前层的所有单词处理后，步数加1（进入下一层）
            steps++;
        }

        // 若队列空了仍未找到目标单词，返回0（无法转换）
        return 0;
    }
}
